package likou;

/**
 * @description: 背包问题
 * 一个容量有限的背包
 * 可以放入x重量的商品 每个商品的重量和价值都不一样
 * 等到价值最大的值
 * @title: BackpackDemo
 * @author: zp
 * @date: 2022/1/17 20:16
 */
public class BackpackDemo {
    public static void main(String[] args) {
        int[] val = {1500, 2000, 3000};
        int[] w = {1, 3, 4};
        int backPackNum = 4;
        System.out.println("最大总价值："+maxValue(val, w, backPackNum));

    }

    /**
     * @description: 贪心算法 获取最大价值
     * @author: zp
     * @date: 2022/1/18 20:17
     * @param: values
     * @param: weights
     * @param: backPackCapacity
     * @return: int
     */
    public static int maxValue(int[] values, int[] weights, int backPackCapacity) {
        int[][] ints = new int[values.length + 1][backPackCapacity + 1];
        int[][] path = new int[values.length + 1][backPackCapacity + 1];
        for (int i = 1; i < ints.length; i++) {
            for (int j = 1; j < ints[0].length; j++) {
                //为什么要减一 因为数组是从1开始的 但是重量是从0开始的 所以需要减一
                //如果重量太大 直接获取上一层的价值 因为上一层的价值已经是这个容量能放下的最大价值物品
                if (weights[i - 1] > j) {
                    ints[i][j] = ints[i - 1][j];
                } else {
                    //如果容量还有剩余 获取这次和上一次的价值作比较 获取最大价值的数据保存到这一位数组当中
                    //ints[i][j] = Math.max(ints[i - 1][j], values[i - 1] + ints[i - 1][j - weights[i - 1]]);
                    if(ints[i - 1][j]<values[i - 1] + ints[i - 1][j - weights[i - 1]]){
                        ints[i][j] = values[i - 1] + ints[i - 1][j - weights[i - 1]];
                        path[i][j] = 1;
                    }else {
                        ints[i][j] = ints[i - 1][j];
                    }
                }
            }
        }
        //输出放入的物品
        int i = path.length-1;
        int j = path[0].length-1;
        while (i>0 && j>0){
            if(path[i][j]==1){
                System.out.printf("把第%d放入背包\n",i);
                j-=weights[i-1];
            }
            i--;
        }

        //最大价值的计算的合在数组的最后一位
        return ints[values.length][backPackCapacity];
    }
}
